-- Author: Timothy Riley
-- Class: CS3022 Programming Paradigms
-- Professor: CDR Shaffer
-- Haskell implementation that implements the mean, median and mode of a list
-- References:
--     http://www.haskell.org/ghc/docs/6.12.3/html/libraries/containers-0.3.0.0/Data-Map.html
--     http://learnyouahaskell.com/chapters
--     http://haskell101.wordpress.com/2008/02/03/count-matches-in-a-list/
-- To execute load into GHCi the type main to run default or statistics []

module Main where
import qualified Data.Map as Map

statistics [] = error "A non empty list is required"
statistics x =  (mean x, median x, mode x)

-- Step 1: Sum the items in the list
-- Step 2: Divide the sum by the length of the list
mean :: (Floating a) => [a] -> a
mean [] = error "A non empty list is required"
mean x = (sum x) / fromIntegral (length x)

-- Step 1: Determine if the list is even or odd
-- Step 2: If Odd
-- Step 2a: Sort the list
-- Step 2b: Obtain the value directly in the middle
-- Step 3: If Even
-- Step 3a: Sort the list
-- Step 3b: Obtain the mean (avg) of the middle two values
median [] = error "A non empty list is required"
median x = if (mod (length x) 2) == 1
                then  (sort x) !! (div (fromIntegral (length x)) 2)
                else mean [(sort x) !! ((div (fromIntegral (length x)) 2) - 1), (sort x) !! (div (fromIntegral (length x)) 2)]

-- Standard quicksort algorithm referenced from CS3022 CDR Shaffer
sort [] = []
sort (x : xs) =
        sort [y | y <- xs, y < x]
                ++ [x]
                ++ sort [z | z <- xs, z >= x]


-- Method used to count the number of times an element appears in a list
-- Designed to be called by the mapWithKey method of Data.Map
-- Referenced from http://haskell101.wordpress.com/2008/02/03/count-matches-in-a-list/
countKey [] key val = 0
countKey (y : ys) key val
        | key == y = 1 + (countKey ys key val)
        | otherwise = countKey ys key val


-- Step 1: Initialize a map with the list elements as the key and the
--         count set to zero ref: Map.fromList
-- Step 2: Interate over the key values calling countKey passing the
--         list to determine how many times the key appears in the list ref Map.mapWithKey
-- Step 3: Convert resulting map to list
-- Step 4: Reverse the tuple values in the list (e.g. [(3,6),(2,7)] => [(6,3),(7,2)]
-- Step 5: Sort the list using quick sort
-- Step 6: Obtain the last item in the list
-- Step 7: Obtain the second item in the tuple (aka: the mode)
mode [] = error "A non empty list is required"
mode x = snd (last (sort [(snd(z), fst(z)) | z <- Map.toList (Map.mapWithKey (countKey x) (Map.fromList [(y,0) | y <- x]))]))

main::IO()
main = do
        let test_list = [1,20,3,1,21,1,5,1,3,1,6,6,6,6,6,1]
        let (mn, mdn, md) = statistics test_list
        let output = "Mean: " ++ show mn ++ ", Median: " ++ show mdn ++ ", Mode: " ++ show md
        putStrLn output